Classification with Scaled Genetic Algorithms in a Coevolutionary Setting

Lothar M. Schmitt

Abstract. This work discusses asymptotic convergence of scaled genetic algorithms in a coevolutionary setting where the underlying population contains fixed numbers of creatures of various types. These types of creatures can act on each other in cooperative or competitive manner. The genetic algorithm uses common mutation and crossover operators as well as proportional fitness selection. By a scaled genetic algorithm, we mean that the mutation and crossover rates have to be annealed to zero in proper fashion over the course of the algorithm, and power-law scaling is used for the fitness function with (unbounded) logarithmic growth in the exponent. In the case that a scaled (non-elitist, non-memory) genetic algorithm is used as function optimizer, it has been shown [Theoret. Comput. Sci. 310, p. 181] that such an algorithm is able to find global optima asymptoticly with probability one. However, in the case of a coevolutionary setting, global optima need not exist. Based upon a properly defined, population-dependent fitness function, the set of creatures of a specific type can be canonically grouped into equivalence classes such that all members of one equivalence class are either inferior or superior to all members of another class. We show that in the situation of a coevolutionary setting, a scaled genetic algorithm at least retains the property of converging to a probability distribution over such populations that contain only copies of one creature from the top-class for every or a selected group of types while on the other hand maintaining a noisy field of test-cases.

LNCS 3103, p. 138 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004